home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / add.m < prev    next >
Encoding:
Text File  |  1992-08-18  |  7.3 KB  |  251 lines
  1.  
  2. #include <stdlib.h>
  3. #ifdef MYDIR
  4. #else
  5. #include "TwoDView.h"
  6. #include "TwoDTSP.h"
  7. #include <appkit/graphics.h>
  8. #endif
  9. #include <math.h>
  10. #include <limits.h>
  11. #include <stdio.h>
  12. #include "tspheaders.h"
  13. #include "prototypes.h"
  14. /************************************************************************/
  15. /* This function implements the Nearest Addition Algorithm for the
  16.    Travelling Salesperson Algorithm.  It provides an approximate optimal
  17.    value rather than the optimal value. 
  18.  
  19.    Reference: Lawler, Lenstra, et. al., The Traveling Salesman [sic] Problem,
  20.              1985, Wiley and Sons, p 157.
  21.  
  22. */
  23. /************************************************************************/
  24. /* Parameters:   TwoDView *self: Ye Old Drawing Object
  25.  
  26.                     float *Data: Pointer to the list of points.
  27.                                  Used to draw intermediate graph.
  28.  
  29.                 float *Distance: Pointer to area that contains the
  30.                                  Distances Between Each Pair of Cities
  31.  
  32.                       int *Tour: Pointer to area that will contain the
  33.                                  indices of the n arcs that are selected 
  34.                                  to be a part of the tour
  35.  
  36.              int NumberOfCities: Number of cities in the problem
  37. */
  38. /************************************************************************/
  39. /************************************************************************/
  40. #ifdef MYDIR
  41. float NearestAddition(float *Distance,int *Tour,int NumberOfCities) {
  42. #else
  43. float NearestAddition(TwoDView *self,float *data,float *Distance,int *Tour,
  44.                         int NumberOfCities) {
  45. #endif
  46. int i,j,k,m,x,y,I,J,
  47.     From,To,BaseCity,ArcEnd,ReplaceIndex,CurrentCity,
  48.     SubTourEnd,TourIndex,NewCity,NotFound;
  49. int *OnTour, *TourCities;
  50. float NewDistance,OptimalValue;
  51.  
  52. /* allocate space for OnTour and TourCities */
  53. OnTour = (int *)malloc(NumberOfCities*sizeof(int));
  54. TourCities = (int *)malloc(NumberOfCities*sizeof(int));
  55. if (OnTour == (int *) 0)
  56.   printf("Malloc for OnTour failed. \n");
  57. if (TourCities == (int *) 0)
  58.   printf("Malloc for OnTour failed. \n");
  59. for (i=0;i<NumberOfCities;i++) {
  60.    OnTour[i] = 0;
  61.  }
  62. for (i=0;i<NumberOfCities;i++) {
  63.    TourCities[i] = 0;
  64.  }
  65.  
  66.  
  67. #ifdef DEBUGMYDIR
  68.  for (i=0;i<(NumberOfCities-1)*NumberOfCities/2;i++) {
  69.    printf("Distance[%d] = %f; \n",i,Distance[i]);
  70.  }
  71.  #endif
  72.  
  73.  /* find the two cities with the minimum distance */
  74.  /* these two cities make up the initial subtour  */
  75.  NewDistance = ClosestCities(Distance,&From,&To,NumberOfCities);
  76.  
  77.  /* if NewDistance doesn't change, there is a problem ... */
  78.  if (NewDistance == INT_MAX) {
  79.    printf("Error no initial subtour found. \n");
  80.  }
  81.  #ifdef DEBUGMYDIR
  82.  else {
  83.    printf("initial subtour \n");
  84.    printf("from %d to %d distance %f \n",From,To,NewDistance);
  85.  }
  86.  #endif
  87.  
  88.  /* OnTour is a list of cities on the tour already. */
  89.  Tour[0] = Tour[3] = From;
  90.  Tour[1] = Tour[2] = To;
  91.  OnTour[From] = OnTour[To] = 1;
  92.  TourCities[0] = From;
  93.  TourCities[1] = To;
  94.  OptimalValue = 2*NewDistance;
  95.  
  96.  SubTourEnd = 1;
  97.  TourIndex = -1;
  98.  NewCity = NumberOfCities;
  99.  NewDistance = INT_MAX; 
  100.  
  101.  /* keep adding cities until you include all NumberOfCities of them */
  102.  while (SubTourEnd < NumberOfCities-1) {
  103.  #ifdef DEBUGMYDIR
  104.    printf("Start of Iteration with %d cities in tour \n",SubTourEnd+1);
  105.  #endif
  106.    /* at the end of this while loop, there will be a new city to insert */
  107.    while (TourIndex < SubTourEnd) {
  108.      /* look at the next city already on the tour */
  109.      TourIndex+=1;
  110.      CurrentCity = TourCities[TourIndex];
  111.  #ifdef DEBUGMYDIR
  112.        printf("Looking at city %d \n",CurrentCity);   
  113.  #endif
  114.      /* look at all arcs starting at CurrentCity */
  115.      I = ArcIndex(CurrentCity,NumberOfCities);
  116.      J = ArcIndex((CurrentCity+1),NumberOfCities);
  117.      for (i=I;i<J;i++) {
  118.        /* j = terminating end of this arc */
  119.        j = i-I+CurrentCity+1;
  120.        /* if the city at the other end isn't already on the tour ...*/
  121.        if (!OnTour[j]) {
  122.          /* Is the arc a new candidate for insertion? */
  123.      k = kfrom(CurrentCity,j,NumberOfCities);
  124.      if (Distance[k] < NewDistance) {
  125.  #ifdef DEBUGMYDIR
  126.        printf("Changing cities from %d to %d \n",NewCity,j);   
  127.        printf("Looking at city %d \n",CurrentCity);   
  128.  #endif
  129.        NewDistance = Distance[k];
  130.        NewCity = j;
  131.            BaseCity = CurrentCity;
  132.      } 
  133.        } 
  134.      }
  135.  
  136.      /* look at all arcs ending at CurrentCity */
  137.      for (m=0;m<CurrentCity;m++) {
  138.        /* if the starting city isn't already on the tour ...*/
  139.        if (!OnTour[m]) {
  140.          /* Is this arc a new candidate for insertion? */
  141.          k = kfrom(m,CurrentCity,NumberOfCities);
  142.          if (Distance[k] < NewDistance) {
  143.  #ifdef DEBUGMYDIR
  144.            printf("Changing cities from %d to %d \n",NewCity,m);   
  145.  #endif
  146.            NewDistance = Distance[k];
  147.        NewCity = m;
  148.            BaseCity = CurrentCity;
  149.      } 
  150.        }
  151.      }
  152.    }
  153.  
  154.    if (NewCity >= NumberOfCities) {
  155.      printf("Error: new city has not been found for tour. \n");
  156.      CurrentCity = SubTourEnd = NumberOfCities;
  157.      OptimalValue = -1;
  158.    }
  159.    else {
  160.      /* find an arc connected to BaseCity, and replace it with
  161.         the new arc. */
  162.      k = 0;
  163.      NotFound = 1;
  164.      while ((k < SubTourEnd) && (NotFound)) {
  165.        if (Tour[2*k] == BaseCity) {
  166.          ArcEnd  = Tour[2*k+1];
  167.          ReplaceIndex = k;
  168.          NotFound = 0;
  169.        }
  170.        if (Tour[2*k+1] == BaseCity) {
  171.          ArcEnd = Tour[2*k];
  172.          ReplaceIndex = k;
  173.          NotFound = 0;
  174.        }
  175.        k+=1;
  176.      }
  177.      
  178.      if (NotFound) {
  179.        printf("Error: Haven't found arc on Tour Ending at %d \n",BaseCity); 
  180.        CurrentCity = SubTourEnd = NumberOfCities;
  181.        OptimalValue = -1;
  182.      }
  183.      else {
  184.        /* arc between BaseCity and ArcEnd is replaced by arc
  185.           between NewCity and ArcEnd. */
  186.  #ifdef DEBUGMYDIR
  187.        printf("replacing arc from %d to %d with %d to %d \n",
  188.                BaseCity,ArcEnd,NewCity,ArcEnd);
  189.  #endif
  190.        Tour[2*ReplaceIndex] = NewCity;
  191.        Tour[2*ReplaceIndex+1] = ArcEnd;
  192.  
  193.        /* update the Optimal Value */
  194.        OptimalValue+=Distance[kfrom(NewCity,ArcEnd,NumberOfCities)] -
  195.                      Distance[kfrom(BaseCity,ArcEnd,NumberOfCities)];
  196.  
  197.        /* add the new arc going from NewCity to BaseCity */
  198.  #ifdef DEBUGMYDIR
  199.        printf("adding arc from %d to %d \n",NewCity,BaseCity);
  200.  #endif
  201.        SubTourEnd+=1;
  202.        Tour[2*SubTourEnd] = NewCity;
  203.        Tour[2*SubTourEnd+1] = BaseCity;
  204.        OnTour[NewCity] = 1;
  205.        TourCities[SubTourEnd] = NewCity;
  206.     
  207.        /* update the Optimal Value */  
  208.        OptimalValue+=NewDistance;
  209.  
  210.  #ifdef DEBUGMYDIR
  211.        printf("addding %f to Opval to get %f \n",NewDistance,OptimalValue);
  212.  #endif
  213.      }
  214.  
  215.      /* get ready to start at the top of the list again */
  216.      TourIndex = -1;
  217.      NewDistance = INT_MAX; 
  218.      NewCity = NumberOfCities; 
  219.  
  220.  #ifdef DEBUGMYDIR
  221.      /* print out current subtour */ 
  222.      for (i=0;i<2*(SubTourEnd+1);i++) {
  223.        printf("i tour %d %d \n",i,Tour[i]);
  224.      }
  225.  #endif
  226.  #ifdef MYDIR
  227.  #else
  228.      /* draw the intermediate tour */
  229.      PSnewinstance();
  230.     for(i=0;i<2*(SubTourEnd+1);i+=2) { 
  231.      x = Tour[i];
  232.      y = Tour[i+1];
  233.      [self drawEdge:X(x):Y(x):X(y):Y(y)];
  234.  
  235.     }
  236.      NXPing();
  237.      [self->optimalValueField setFloatValue: OptimalValue at: 0];
  238.      usleep(self->drawTime);
  239. #endif
  240.     
  241. }
  242. }
  243.  
  244. /* clean up */
  245. free(OnTour);
  246.  
  247. /* return the optimal value */
  248. return(OptimalValue);
  249. }
  250.         
  251.